#include "combinationFunc.h"

template <class T>
vector<vector<T> > combination(vector<T> v,int m){

	vector<vector<T> > vecs;
	int vSize=static_cast<int> (v.size());
	
	if (vSize==m){
		vecs.push_back(v);
		return vecs;
	}
	if (m==1){
		vector<T>::const_iterator itv;
		for (itv=v.begin();itv!=v.end();++itv){
			vecs.push_back(vector<T>(1,*itv));
		}

		return vecs;
	}
	
	T first=v.front();
	v.erase(v.begin());
	
	vector< vector<T> >::iterator itvv;
	vecs=combination(v,m-1);
	for (itvv=vecs.begin();itvv!=vecs.end();++itvv){
		itvv->push_back(first);
	}
	vector<vector<T> > toCombine;
	toCombine=combination(v,m);
	vecs.insert(vecs.end(),toCombine.begin(),toCombine.end());
	
	return vecs;
}